/**
 * Created with IntelliJ IDEA.
 * Description: 复习滑动窗口
 * User: DELL
 * Date: 2024-03-15
 * Time: 23:55
 */
public class TestDemo {
    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 5, 6, 7, 8, 9};
        int[] max = new int[arr.length];
        process(arr, max, arr.length, 3);
        for (int i = 0; i < arr.length; i++) {
            System.out.printf(max[i] + " ");
        }
        System.out.println();
    }

    private static void process(int[] arr, int[] max, int n, int a) {
        int[] temp = new int[n];
        int left = 0;
        int right = -1;
        for (int i = 0; i < n; i++) {
            if (left <= right && temp[left] <= i - a) {
                left++;
            }
            while (left <= right && arr[temp[right]] <= arr[i]) {
                right--;
            }
            temp[++right] = i;
            if (i >= a - 1) {
                max[i] = arr[temp[left]];
            }
        }
    }
}
